import java.util.LinkedList;
import java.util.List;

/**
 * 17. 电话号码的字母组合
 * https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
 */
class Solution2 {
    List<String> ret;
    StringBuilder path;
    String[] hash;
    public List<String> letterCombinations(String digits) {
        ret = new LinkedList<>();
        if(digits.length() == 0) return ret;
        path = new StringBuilder();
        hash = new String[12];
        hash[2] = "abc";
        hash[3] = "def";
        hash[4] = "ghi";
        hash[5] = "jkl";
        hash[6] = "mno";
        hash[7] = "pqrs";
        hash[8] = "tuv";
        hash[9] = "wxyz";

        dfs(digits, 0);

        return ret;
    }

    public void dfs(String digits, int pos) {
        if(path.length() == digits.length()) {
            ret.add(path.toString());
            return;
        }

        int cur = digits.charAt(pos) - '0';
        String tmp = hash[cur];

        for(int i = 0; i < tmp.length(); i++) {
            path.append(tmp.charAt(i));
            dfs(digits, pos + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}